package 堆;

import java.util.ArrayList;
import java.util.List;

/**
 * 基于ArrayList动态数组实现的大顶堆
 */
public class MyHeap {
    //动态数组
    private List<Integer> list;
    //数组中元素的个数
    private int size;

    public MyHeap() {
        this(10);
    }

    public MyHeap(int size) {
        list = new ArrayList<>(size);
    }

    /**
     * 获取父节点位置的方法
     * @param k
     * @return
     */
    private int parent(int k){
        return (k-1) >> 1;
    }

    /**
     * 获取左孩子坐标的方法
     * @param k
     * @return
     */
    private int leftChild(int k){
        return (k << 1) + 1;
    }

    /**
     * 获取右孩子坐标的方法
     * @param k
     * @return
     */
    private int rightChild(int k){
        return (k << 1 ) + 2;
    }

    /**
     * 判空方法
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 获取堆中元素个数的方法
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 元素的上浮操作
     * @param k
     */
    public void sifeUp(int k){
        while (k > 0 && list.get(k) > list.get(parent(k))){
            swap(k,parent(k));
            k = parent(k);
        }
    }

    /**
     * 交换两个元素的位置
     * @param k
     * @param parent
     */
    private void swap(int k, int parent) {
        int temp = list.get(k);
        int cue = list.get(parent);
        list.set(k,cue);
        list.set(parent,temp);
    }

    /**
     * 添加元素的此操作
     * @param val
     */
    public void add(int val){
        list.add(val);
        size++;
        sifeUp(size-1);
    }

    /**
     * 获取最大值的操作
     * @return
     */
    public int getMaxVal(){
        //获取最大值
        int max = list.get(0);
        //将树最后一个元素设置为堆顶元素
        list.set(0,list.get(size-1));
        //删除最后一个元素
        list.remove(size-1);
        size--;
        //元素的下浮操作
        sifeDown(0);
        return max;
    }

    /**
     * 元素下沉操作
     * @param k
     */
    private void sifeDown(int k) {
        //如果k在size范围内
        while (leftChild(k) < size){
            //获取k的左孩子位置
            int left = leftChild(k);
            //判断是否存在右孩子，并找到左右节点的最大值
            if (left+1 < size && list.get(left) <= list.get(left+1)){
                left++;
            }
            if (list.get(k) >= list.get(left)){
                break;
            }else {
                swap(k,left);
            }
            k = left;
        }
    }

    public void arrHeapify(int[] arr){
        //1,将数组全部到集合中
        for (int i:arr) {
            list.add(i);
            size++;
        }
        //2，从最后一个非叶子节点开始下沉
        for (int i = parent(size-1); i >= 0 ; i--) {
            sifeDown(i);
        }
    }
    public String toString(){
        return list.toString();
    }
}

class TestHeap{
    public static void main(String[] args) {
        MyHeap myHeap = new MyHeap();
        int[] arr = new int[]{12,34,54,23,3,43,13,54,33};
        myHeap.arrHeapify(arr);
        System.out.println(myHeap);
//        myHeap.add(62);
//        myHeap.add(40);
//        myHeap.add(30);
//        myHeap.add(28);
//        myHeap.add(16);
//        myHeap.add(22);
//        myHeap.add(13);
//        myHeap.add(19);
//        myHeap.add(17);
//        myHeap.add(15);
//        myHeap.add(52);
//        System.out.println(myHeap.toString());
//        System.out.println(myHeap.getMaxVal());
//        System.out.println(myHeap);
//        while (!myHeap.isEmpty()){
//            System.out.print(myHeap.getMaxVal()+" ");
//        }
    }
}
